package main

import "fmt"

func main() {
	res := levelOrder(&TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	})
	for _, i := range res {
		for _, j := range i {
			fmt.Print(" ", j)
		}
		fmt.Println()
	}
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) (ans [][]int) {
	if root == nil {
		return nil
	}
	var queue [](*TreeNode)
	queue = append(queue, root)
	var level int
	for length := len(queue); length != 0; length = len(queue) {
		ans = append(ans, nil)
		for _, v := range queue {
			ans[level] = append(ans[level], v.Val)
			if v.Left != nil {
				queue = append(queue, v.Left)
			}
			if v.Right != nil {
				queue = append(queue, v.Right)
			}
		}
		queue = queue[length:]
		level++
	}
	return ans
}
